Search for: All records

Quantifying network reliability is a hard problem, proven to be #P-complete [1]. For real-world network planning and decision making, approximations for the network reliability problem are necessary. This study shows that tensor network contraction (TNC) methods can quickly estimate an upper bound of All Terminal Reliability, RelATR(G), by solving a superset of the network reliability problem: the edge cover problem, EC(G). In addition, these tensor contraction methods can exactly solve source-terminal (S-T) reliability for the class of directed acyclic networks, RelS−T (G). The computational complexity of TNC methods is parameterized by treewidth, significantly benefitting from recent advancements in approximate tree decomposition algorithms [2]. This parameterization does not rely on the reliability of the graph, which means these tensor contraction methods can determine reliability faster than Monte Carlo methods on highly reliable networks, while also providing exact answers or guaranteed upper bound estimates. These tensor contraction methods are applied to grid graphs, random cubic graphs, and a selection of 58 power transmission networks [3], demonstrating computational efficiency and effective approximation using EC(G). 

Infrastructure networks offer critical services to modern society. They dynamically interact with the environment, operators, and users. Infrastructure networks are unique engineered systems, large in scale and high in complexity. One fundamental issue for their reliability assessment is the uncertainty propagation from stochastic disturbances across interconnected components. Monte Carlo simulation (MCS) remains approachable to quantify stochastic dynamics from components to systems. Its application depends on time efficiency along with the capability of delivering reliable approximations. In this paper, we introduce Quasi Monte Carlo (QMC) sampling techniques to improve modeling efficiency. Also, we suggest a principled Monte Carlo (PMC) method that equips the crude MCS with Probably Approximately Correct (PAC) approaches to deliver guaranteed approximations. We compare our proposed schemes with a competitive approach for stochastic dynamic analysis, namely the Probability Density Evolution Method (PDEM). Our computational experiments are on ideal but complex enough source-terminal (S-T) dynamic network reliability problems. We endow network links with oscillators so that they can jump across safe and failed states allowing us to treat the problem from a stochastic process perspective. We find that QMC alone can yield practical accuracy, and PMC with a PAC algorithm can deliver accuracy guarantees. Also, QMC is more versatile and efficient than the PDEM for network reliability assessment. The QMC and PMC methods provide advanced uncertainty propagation techniques to support decision makers with their reliability problems.